package com.wwz.leetcode;

import com.wwz.common.ListNode;
import org.junit.Test;

/**
 * @description: 反转链表 II
 * @author: Sailor
 * @date: 2023-12-27 09:25:03
 */
public class LeetCode92_1 {
    @Test
    public void test() {
        ListNode listNode = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5)))));
        ListNode listNode1 = reverseBetween(listNode, 2, 4);
    }

    public ListNode reverseBetween(ListNode head, int left, int right) {
        ListNode pre = new ListNode();
        // 前驱指针指向 head
        pre.next = head;
        // 定义双指针
        ListNode g = pre;
        ListNode p = pre.next;
        // 异动到指定位置
        for (int i = 0; i < left - 1; i++) {
            g = g.next;
            p = p.next;
        }
        // 头插法
        for (int i = 0; i < right - left; i++) {
            ListNode removeNode = p.next;
            p.next = removeNode.next;
            removeNode.next = g.next;
            g.next = removeNode;
        }
        return pre.next;
    }
}
